/*
 * ============================================================================
 * 数组 (Array) - C语言实现
 * ============================================================================
 * 
 * 【核心定义】
 * 数组是一种线性数据结构，在连续的内存空间中存储相同类型的元素集合。
 * 支持通过索引进行O(1)时间复杂度的随机访问。
 * 
 * 【内存布局】
 * 静态数组:
 *   int arr[5] = {10, 20, 30, 40, 50};
 *   
 *   内存地址:  0x1000   0x1004   0x1008   0x100C   0x1010
 *              +--------+--------+--------+--------+--------+
 *   值:        |   10   |   20   |   30   |   40   |   50   |
 *              +--------+--------+--------+--------+--------+
 *   索引:          0        1        2        3        4
 * 
 * 动态数组:
 *   int *arr = (int*)malloc(5 * sizeof(int));
 *   堆内存中分配，需要手动管理内存
 * 
 * 【时间复杂度】
 * - 访问: O(1)  - 直接通过索引计算地址
 * - 搜索: O(n)  - 需要遍历
 * - 插入: O(n)  - 需要移动元素
 * - 删除: O(n)  - 需要移动元素
 * 
 * 【空间复杂度】O(n)
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// ============================================================================
// 动态数组结构定义
// ============================================================================
typedef struct {
    int *data;      // 指向数据的指针
    int size;       // 当前元素数量
    int capacity;   // 当前容量
} DynamicArray;

// ============================================================================
// 动态数组基本操作
// ============================================================================

// 创建动态数组
DynamicArray* createArray(int initial_capacity) {
    DynamicArray *arr = (DynamicArray*)malloc(sizeof(DynamicArray));
    arr->data = (int*)malloc(initial_capacity * sizeof(int));
    arr->size = 0;
    arr->capacity = initial_capacity;
    return arr;
}

// 在末尾添加元素
void append(DynamicArray *arr, int value) {
    // 如果容量不足，扩容为原来的2倍
    if (arr->size >= arr->capacity) {
        arr->capacity *= 2;
        arr->data = (int*)realloc(arr->data, arr->capacity * sizeof(int));
    }
    arr->data[arr->size++] = value;
}

// 在指定位置插入元素
void insertAt(DynamicArray *arr, int index, int value) {
    if (index < 0 || index > arr->size) {
        printf("错误: 索引越界\n");
        return;
    }
    
    if (arr->size >= arr->capacity) {
        arr->capacity *= 2;
        arr->data = (int*)realloc(arr->data, arr->capacity * sizeof(int));
    }
    
    // 将index及之后的元素向后移动
    for (int i = arr->size; i > index; i--) {
        arr->data[i] = arr->data[i-1];
    }
    arr->data[index] = value;
    arr->size++;
}

// 删除指定位置的元素
void deleteAt(DynamicArray *arr, int index) {
    if (index < 0 || index >= arr->size) {
        printf("错误: 索引越界\n");
        return;
    }
    
    // 将index之后的元素向前移动
    for (int i = index; i < arr->size - 1; i++) {
        arr->data[i] = arr->data[i+1];
    }
    arr->size--;
}

// 获取指定位置的元素
int get(DynamicArray *arr, int index) {
    if (index < 0 || index >= arr->size) {
        printf("错误: 索引越界\n");
        return -1;
    }
    return arr->data[index];
}

// 查找元素，返回索引
int search(DynamicArray *arr, int value) {
    for (int i = 0; i < arr->size; i++) {
        if (arr->data[i] == value) {
            return i;
        }
    }
    return -1;  // 未找到
}

// 打印数组
void printArray(DynamicArray *arr) {
    printf("[");
    for (int i = 0; i < arr->size; i++) {
        printf("%d", arr->data[i]);
        if (i < arr->size - 1) printf(", ");
    }
    printf("]\n");
}

// 释放数组内存
void freeArray(DynamicArray *arr) {
    free(arr->data);
    free(arr);
}

// ============================================================================
// 应用场景1: 查找表 - 快速访问
// ============================================================================
void example_lookup_table() {
    printf("\n=== 应用场景1: 查找表 ===\n");
    printf("场景: 存储每月天数，通过月份索引快速查询\n\n");
    
    int days_in_month[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    
    int month = 7;  // 8月
    printf("第%d个月有%d天\n", month + 1, days_in_month[month]);
    printf("优势: O(1)时间复杂度，直接索引访问\n");
}

// ============================================================================
// 应用场景2: 缓存实现 - LRU缓存的数据存储部分
// ============================================================================
typedef struct {
    int key;
    int value;
} CacheEntry;

void example_cache() {
    printf("\n=== 应用场景2: 简单缓存 ===\n");
    printf("场景: 缓存最近访问的数据\n\n");
    
    CacheEntry cache[5];
    int cache_size = 0;
    
    // 添加缓存条目
    cache[cache_size].key = 101;
    cache[cache_size].value = 500;
    cache_size++;
    
    cache[cache_size].key = 102;
    cache[cache_size].value = 600;
    cache_size++;
    
    // 查询缓存
    int search_key = 101;
    for (int i = 0; i < cache_size; i++) {
        if (cache[i].key == search_key) {
            printf("缓存命中: key=%d, value=%d\n", search_key, cache[i].value);
            break;
        }
    }
    printf("优势: 连续内存，缓存友好，遍历速度快\n");
}

// ============================================================================
// 应用场景3: 矩阵运算 - 图像处理
// ============================================================================
void example_matrix() {
    printf("\n=== 应用场景3: 矩阵运算 ===\n");
    printf("场景: 图像像素数据存储和处理\n\n");
    
    // 3x3 矩阵表示一个小图像区域
    int image[3][3] = {
        {255, 200, 150},
        {180, 220, 160},
        {140, 190, 210}
    };
    
    printf("原始图像数据:\n");
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            printf("%3d ", image[i][j]);
        }
        printf("\n");
    }
    
    // 简单的图像处理：降低亮度
    printf("\n降低亮度后:\n");
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            image[i][j] = image[i][j] * 0.8;  // 降低20%亮度
            printf("%3d ", image[i][j]);
        }
        printf("\n");
    }
    printf("优势: 连续内存访问，适合批量处理\n");
}

// ============================================================================
// 主函数 - 演示所有功能
// ============================================================================
int main() {
    printf("╔════════════════════════════════════════╗\n");
    printf("║   数组 (Array) - C语言实现            ║\n");
    printf("╚════════════════════════════════════════╝\n");
    
    // 基本操作演示
    printf("\n--- 动态数组基本操作 ---\n");
    DynamicArray *arr = createArray(5);
    
    printf("1. 添加元素: ");
    append(arr, 10);
    append(arr, 20);
    append(arr, 30);
    append(arr, 40);
    printArray(arr);
    
    printf("2. 在索引1插入元素25: ");
    insertAt(arr, 1, 25);
    printArray(arr);
    
    printf("3. 删除索引2的元素: ");
    deleteAt(arr, 2);
    printArray(arr);
    
    printf("4. 查找元素40: 索引 = %d\n", search(arr, 40));
    printf("5. 获取索引2的元素: %d\n", get(arr, 2));
    
    printf("\n当前数组状态:\n");
    printf("  大小: %d\n", arr->size);
    printf("  容量: %d\n", arr->capacity);
    printf("  内存使用: %d 字节\n", arr->capacity * sizeof(int));
    
    // 应用场景演示
    example_lookup_table();
    example_cache();
    example_matrix();
    
    // 优势与局限
    printf("\n╔════════════════════════════════════════╗\n");
    printf("║   优势与局限                           ║\n");
    printf("╚════════════════════════════════════════╝\n");
    printf("\n✅ 优势:\n");
    printf("  1. O(1)随机访问速度\n");
    printf("  2. 内存连续，缓存友好\n");
    printf("  3. 简单高效，硬件支持好\n");
    printf("  4. 空间利用率高\n");

    printf("\n⚠️ 局限:\n");
    printf("  1. 固定大小（静态数组）或需要扩容（动态数组）\n");
    printf("  2. 插入/删除需要移动大量元素，O(n)复杂度\n");
    printf("  3. 扩容时需要复制所有数据\n");
    printf("  4. 可能造成内存碎片\n");
    
    printf("\n💡 最佳使用场景:\n");
    printf("  - 需要频繁随机访问元素\n");
    printf("  - 数据量相对固定\n");
    printf("  - 很少进行插入/删除操作\n");
    printf("  - 查找表、缓存、矩阵运算\n");
    
    // 清理
    freeArray(arr);
    
    return 0;
}
